package com.mgq.algorithm.link;

import java.util.HashMap;

/**
 * @author MaGuangQi
 * 判断一个链表是否有环 141
 * @date 2021-12-30 17:44
 **/
public class LinkedListCycle_141 {
    /**
     * 双指针
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next.next;
        while (fast != null&& fast.next!=null) {
            if (slow == fast) {
                return true;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return false;
    }

    /**
     *使用哈希表,key和value都是ListNode.每次加入之前判断,hash表中是否存在.存在就说明有环
     * 可以使用hashset.
     * @param head
     * @return
     */
    public boolean hasCycle2(ListNode head) {
        HashMap<ListNode,ListNode> hashMap = new HashMap<>();
        while (head != null) {
            if (hashMap.get(head)!=null&&hashMap.get(head)==head) {
                return true;
            }
            hashMap.put(head,head);
            head=head.next;
        }
        return false;
    }
}
